#include<cpp.h>
#include<time.h>
using namespace std;
typedef pair<int, int> pii; 
typedef vector<int> ve; 

//快速排序
class QSort  
{
public:
	QSort(ve& a):_a(a) 
	{
		srand(time(nullptr)); 
		qsort(0, a.size()-1);
	}
	void show()   
	{
		for (auto x : _a)  
			cout << x << " ";   
	}
private:
	int getkey(int begin, int end)
	{
		int t = begin + rand() % (end - begin + 1);
		return _a[t];
	}
	void qsort(int begin ,int end )
	{
		if (begin >= end)return;
		int key = getkey(begin, end);    
		int i = begin - 1;  
		int j = end + 1;
		int k = begin;  
		while (k < j)   
		{
			if (_a[k] < key)swap(_a[k++], _a[++i]);
			else if (_a[k] == key)k++;
			else swap(_a[k], _a[--j]);     
		}
		qsort(begin, i);
		qsort(j , end);      
	}

private:
	ve _a;
};

int main()
{
	ve num = { 5,4,6,8,1,6,4,4,5,0,1,5,4,44,15, };
	QSort s(num); 
	s.show(); 
	return 0;
}
